# candidates=[10,1,2,7,6,1,5]
# target=8
candidates=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
target=27
# candidates = [2]
# target = 1
#方法很容易超时
#深度优先遍历
def dfs(candidates,target,ans,path,start_index,sum_1):
    if sum_1==target:
        ans.append(path[:])
        print(path)
        return None
    for i in range(start_index,len(candidates)):
        if sum_1+candidates[i]>target:
            break
        if i>start_index and candidates[i-1]==candidates[i]:
            continue
        path.append(candidates[i])
        dfs(candidates,target,ans,path,i+1,sum_1+candidates[i])
        path.pop()
def combinationSum2(candidates,target):
    #返回列表的长度
    candidates_len=len(candidates)
    if candidates_len==0:
        return []
    #用来存放结果的矩阵
    ans=[]
    #路径矩阵
    path=[]
    candidates.sort()
    dfs(candidates,target,ans,path,0,0)
    print(ans)
combinationSum2(candidates,target)
